from collections import Counter
from itertools import permutations

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        """
        计算活字字模可以印出的非空字母序列的数目
        使用DFS + 回溯法
        """
        count = Counter(tiles)
        tile = set(tiles)

        def dfs(i):
            if i == 0:
                return 1
            res = 1
            for t in tile:
                if count[t] > 0:
                    count[t] -= 1
                    res += dfs(i - 1)
                    count[t] += 1
            return res

        return dfs(len(tiles)) - 1

def brute_force_solution(tiles: str) -> int:
    """暴力解法：生成所有可能的排列组合"""
    if not tiles:
        return 0
    
    result = set()
    for length in range(1, len(tiles) + 1):
        for perm in permutations(tiles, length):
            result.add(''.join(perm))
    
    return len(result)

def test_algorithm():
    """测试算法"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        ("AAB", 8),
        ("AAABBC", 188),
        ("V", 1),
        ("", 0),
        ("A", 1),
        ("ABC", 15)
    ]
    
    print("算法测试结果:")
    print("=" * 30)
    
    for tiles, expected in test_cases:
        result = solution.numTilePossibilities(tiles)
        status = "✓" if result == expected else "✗"
        print(f"{status} 输入: '{tiles}', 期望: {expected}, 实际: {result}")

if __name__ == "__main__":
    test_algorithm() 